#深度优先遍历的栈写法
grid=[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
#深度优先遍历：栈实现
def maxAreaOfIsland(grid):
    '''
    :param grid:一个图
    :return: 最大的岛屿面积
    '''
    direction = [-1, 0, 1, 0, -1]
    area=0
    #要遍历全图
    grid_row=len(grid)  #为整个图的行数
    grid_col=len(grid[0]) #图的列数
    for i in range(grid_row):
        #外圈循环控制行数
        for j in range(grid_col):
            island=[]
            #内圈循环控制列数
            if grid[i][j]==1:
                #当前这个位置是一块土地
                local_area=1
                #此处已经遍历过了
                grid[i][j]=0
                island.append([i,j])
                while island:
                    #如果栈中存在元素
                    [r,c]=island.pop(0)
                    for k in range(4):
                        x=r+direction[k]
                        y=c+direction[k+1]
                        if x>=0 and x<grid_row and y>=0 and y<grid_col and grid[x][y]==1:
                            local_area+=1
                            grid[x][y]=0
                            island.append([x,y])
                area=max(area,local_area)
    print(area)

direction=[-1,0,1,0,-1]
def maxAreaOfIsland_1(grid):
    #主函数
    # if not grid or not grid[0]:
    #     return 0
    max_area=0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j]==1:
                max_area=max(max_area,dfs(grid,i,j))
    return max_area

def dfs(grid,r,c):
    #辅函数
    # if grid[r][c]==0:
    #     return 0
    grid[r][c]=0
    local_area=1
    for k in range(4):
        x=r+direction[k]
        y=c+direction[k+1]
        if x>=0 and x<len(grid) and y>=0 and y<len(grid[0]) and grid[x][y]==1:
            local_area+=dfs(grid,x,y)
    return local_area
# maxAreaOfIsland(grid)
print(maxAreaOfIsland_1(grid))
